C++ – what’s the difference between list.sort and std::sort – iTecNote

std::sort requires random access iterators, which std::list does not provide. Consequently, std::list and std::forward_list implement their own member functions for sorting which work with their weaker iterators. The complexity guarantees of those member functions are worse than those of the more efficient general algorithm.[Whoops: see comments.]

Moreover, the member functions can take advantage of the special nature of the list data structure by simply relinking the list nodes, while the standard algorithm has to perform something like swap (or something to that effect), which requires object construction, assignment and deletion.

Note that remove() is a similar case: The standard algorithm is merely some iterator-returning rearrangement, while the list member function performs the lookup and actual removal all in one go; again thanks to being able to take advantage of the knowledge of the list's internal structure.